#include<stdio.h>
#include<stdlib.h>

typedef struct BiTNode{
	char data;
	struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;

typedef struct Node{
	char data;
	int left,right;
}node;

BiTree createBiTree(node* a,int index){
	if(index==0) return NULL;
	BiTree t=(BiTree)malloc(sizeof(BiTNode));
	t->data=a[index].data;
	t->lchild=createBiTree(a,a[index].left);
	t->rchild=createBiTree(a,a[index].right);
	return t;
}

void PreOrderTraverse(BiTree t){
	if(t!=NULL){
		printf("%c",t->data);
		PreOrderTraverse(t->lchild);
		PreOrderTraverse(t->rchild);
	}
}

void InOrderTraverse(BiTree t){
	if(t!=NULL){
		InOrderTraverse(t->lchild);
		printf("%c",t->data);
		InOrderTraverse(t->rchild);
	}
}

void PostOrderTraverse(BiTree t){

	if(t!=NULL){
		PostOrderTraverse(t->lchild);
		PostOrderTraverse(t->rchild);
		printf("%c",t->data);
	} 
}

int main(){
	int n;
	scanf("%d",&n);
	node* nums = (node*)malloc(sizeof(node)*(n+1));
	for(int i=1;i<=n;i++){
	    scanf(" %c %d %d",&(nums[i].data),&(nums[i].left),&(nums[i].right));
	}
	BiTree t = createBiTree(nums,1);
	PreOrderTraverse(t);
	printf("\n");
	InOrderTraverse(t);
	printf("\n");
	PostOrderTraverse(t);
	printf("\n");
	return 0;
}